UVa/572 - Oil deposits/1959.cpp

   1 /*
   2   Problem:
   3   572 - Oil deposits (UVa Online Judge)
   4   1959 - Oil deposits (TJU Online Judge)
   5
   6   Author: Andrés Mejía-Posada (http://github.com/andmej/acm)
   7   Algorithm: Depth-first search
   8  */
   9 #include <iostream>
  10
  11 using namespace std;
  12
  13 int di[] = {-1, -1, -1, +0, +1, +1, +1, +0};
  14 int dj[] = {-1, +0, +1, +1, +1, +0, -1, -1};
  15
  16 int r, c;
  17
  18 char g[100][100];
  19 bool v[100][100];
  20
  21 void dfs(const int &i, const int &j){
  22   if ( (0 <= i && i < r && 0 <= j && j < c) == false){
  23     return;
  24   }
  25   if (v[i][j] || g[i][j] == '*') return;
  26
  27   v[i][j] = true;
  28
  29   for (int k=0; k<8; ++k){
  30     dfs(i + di[k], j + dj[k]);
  31   }
  32
  33 }
  34
  35 int main(){
  36   while (cin >> r >> c && (r+c)){
  37     for (int i =0; i<r; ++i){
  38       for (int j=0; j<c; ++j){
  39         cin >> g[i][j];
  40         v[i][j] = false;
  41       }
  42     }
  43
  44     int t = 0;
  45     for (int i =0; i<r; ++i){
  46       for (int j=0; j<c; ++j){
  47         if (!v[i][j] && g[i][j] == '@'){
  48           ++t;
  49           dfs(i, j);
  50         }
  51       }
  52     }
  53
  54     cout << t << endl;
  55   }
  56   return 0;
  57 }